A common image processing operation is to segment an image into regions having distinct characteristics, such as the different objects in an image. For example, in an image compression scheme the image may be segmented into relatively large regions which can be described in terms of their boundaries and additional characteristics such as texture. This enables the image to be transmitted more efficiently. In pattern recognition and image analysis, an image may be decomposed into the major objects in the scene, and then information describing these objects, such as their edges, is passed to subsequent processing.
In order to separate an image into objects of different scale (size) it is common to perform a multiscale decomposition using some form of spatial filtering (for an extensive review see Lindeberg, 1994 Scale-space theory in computer vision"). In this approach, filters are used to produce images that have been filtered to a range of scales (so objects of smaller scale than the filter are attenuated or removed). The advantages of these multiscale representations crystallised in the 1980's when the concept of `scale-space` emerged (Witkin, 1983, "Scale space filtering" 8th Int Joint Conf Artificial Intelligence).
The key point about scale-space representations is that objects in a scene are usually represented by local intensity extrema (maxima or minima) bounded by edges. A large object can be located either by finding the corresponding extremum (zero crossings of the first derivative) or the corresponding edges (zero crossings of the second derivative). However, this is only reliable if the image is first smoothed with a filter in order to remove fine detail and noise. It is not sufficient to apply any filtering (convolution) operator for it is very desirable that the smoothing does not introduce any new extrema and that the intensity of fine scale features is attenuated monotonically as the filtering scale increases. This property is known as scale-space causality, and is fundamental to an effective scale-space decomposition for use in image analysis etc. Furthermore, most filtering operators do not achieve scale space causality.
Initially, attention was focused on one dimensional signals and it was shown that the only linear (convolution) filters that exhibit this scale space property are Gaussian (diffusion equation related) convolution filters (Yuille and Poggio, 1987 "Scaling Theorems for Zero Crossings", IEEE Trans on Pattern Analysis and Machine Intelligence 9:15-25). Gaussian convolution, implemented as a set of increasing scale difference of Gaussians, Laplacian of Gaussians etc, had already been proposed as a way to decompose a two-dimensional image into a number of scale related "spatial" channels (Marr 1982 Vision" W. H. Freeman and Co). These methods were used to segment an image into regions and, by higher level classification stages, to analyze the image content. However, they only approximated the scale-space causality property for multidimensional signals.
Later it was realised that Gaussian convolution in one dimension simply represents a particular solution to the heat or diffusion equation (Koenderink, 1984, "The structure of Images", Biological Cybemetics 50:363:370). Solving these equations using a 2-D formulation leads to a method of performing a scale-space decomposition in 2-D that conforms to the scale-space causality property. This approach is known as `diffusion based` imaging. However, there are problems with the diffusion based approach. The two most apparent ones are that: 1) At large scales the edges of objects are not well preserved, yet it is edges that are important for many tasks such as pattern recognition; 2) Diffusion based systems are computationally expensive, so are slow or extensive.
An additional branch of the literature that is relevant to the current invention is the behaviour of `connected-set` operators that are used for the processing, coding and recognition of images (Serra, J and Salembier, P 1993, "Connected operators and pyramids" SPIE 2030:63-76). This paper considers the processing of zones of connected pixels of the same intensity value within an image. These form a partition of the image that can be represented as a graph. It also includes some discussion of the effects of morphological operators and other operators that depend on area, geodesic distance etc on connected sets. Some algorithms for the implementation of morphological operators on graphs have also been described (Vincent, L 1989 "Graphs and mathematical morphology" Signal Processing 16:365-388).
A feature of these papers is that they focus or configuring the filters in such a way as to provide apparent computational advantages (see also Vincent L. 1993 "Grayscale area openings and closings, their efficient implementation and applications to signal processing" eds. Jerra and Salembier pages 22-27, ISBN 84-7653-271-7, and Vincent L. 1992 "Morphological area openings and closings for Grayscale images" Proc. NATO Shape in Picture Workshop Driebergen, Springer Verlag pages 197-207).
However, as a result, such filters (known as opening and closing filters) have been found to be sensitive to image degradations, such as noise, which can be of either positive or negative polarity.
Clearly, it would be desirable to provide a filter which is more robust to signal degradation but which presents no significant increase in computational demands compared with these previously proposed filters.
A technique for data processing, related to the current invention, has been described inter alia in PCT/GB94/00080. This describes an alternative method for performing a scale-space decomposition using ordinal value filters (such as median, erosion, dilation, opening, closing, open-close and close-open operators) at each filtering scale, called a `Datasieve`. In this method, the signal or image is passed through a cascade of ordinal value filters of increasing filtering scale such that the output of one filter feeds the input to the next filter in the cascade. We have proved that when applied to one-dimensional signals these methods conform to scale space causality and have other attractive properties such as resilience to noise and the ability to retain the edge definition of larger scale features. It can be shown that each filter in the cascade removes extrema in the signal that have extent equal to the current filtering scale.
However, when the Datasieve, as described in the above patent application, is applied to multidimensional signals (either by applying 1-D filtering at multiple orientations or by applying multi-D filtering using multi-D ordinal value filters), scale-space causality may not be preserved, and consequently this form of decomposition is sometimes not ideal in terms of its ability to reliably segment an image into different objects. An additional problem with filtering using multidimensional ordinal value filters is that sharp corners of objects tend to be removed by the filtering at a lower scale than the main body of the object, which is unsatisfactory for image analysis applications (though this problem has been addressed by reconstruction filters (Salembier P. and Kunt M. "Size sensitive multiresolution decomposition of images with rank order based filters" Signal Processing 27 (1992) 205-241)).
It is an object of the present invention to provide an improved method and apparatus for processing multidimensional signal that does not suffer from these particular disadvantages.